Computer systems are typically provided with a small-capacity high-speed internal memory (cache) that is separate from an outside memory (main memory). High-speed reading of information is enabled by copying a portion of the information that is stored in the outside memory to the cache and then, when accessing this information, reading from the cache rather than from the outside memory. A cache is faster and more expensive than an outside memory, and the storage capacity of the cache is therefore normally far smaller than an outside memory. A cache includes a plurality of cache lines, and the copying of information from an outside memory to the cache is executed in line units. The memory space of the outside memory is therefore divided by cache line units and the divided memory areas are assigned in order to cache lines. The capacity of the cache is smaller than the capacity of the outside memory, and memory areas of the outside memory are therefore repeatedly assigned to the same cache lines. When the first access is performed to a particular address, the information of this address (data or program) is copied to the corresponding cache line in the cache, and when the next access is performed to the same address, the information is read directly from the cache. However, when programs (=instruction code strings) that are arranged at different addresses of the outside memory are assigned to the same cache line during operation of a program, the necessity arises for copying an instruction code string to the cache each time these instruction code strings are alternately read. Such cases are referred to as “instruction cache conflicts.” Frequent occurrence of instruction cache conflicts results in the problem of slower execution of a program. To provide a solution to this problem, arrangement methods are being researched in which instruction code strings that have a high potential of operating in the same time interval are not placed on the same cache lines. Although caches include both instruction caches and data caches, the above-described problem of reading instruction code strings occurs with instruction caches. In addition, although there are typically three types of cache memory mapping methods: the direct scheme, the set-associative scheme, and the full-associative scheme, the above-described problem of cache conflicts is basically the same regardless of which scheme is considered, and the following explanation therefore will be performed on direct mapping by way of example.
To date, as a solution to the problem of instruction cache conflicts, there is a method that focuses on the composition of a program in function units and that thus defines a “function strength” that indicates the number of calls among functions or the number of calls of a specific function call pattern such that functions for which function strength is high (i.e., having a high probability of being read together) are not assigned to the same instruction cache lines. For example, Patent Document 1 discloses a method of finding by means of provisional arrangement, among functions, functions for which the number of executions in a specific pattern is high such as when a plurality of functions are called in a series or are called in a loop. Patent Document 2 discloses a method of, based on a dynamic function flow in which the call order of functions at the time of executing a program made up of a plurality of functions is represented as a time series, generating information of function strength such that information is included regarding the call relations at the times of execution between any function among the functions and all other functions and then, based on the information of function strength, arranging the functions in the memory space to reduce instruction cache conflicts.